package com.atguigu.Kruskal;


import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

/**
 * @author tbwtbw
 * @create 2021-11-26 18:51
 */
public class KruskalCase {

    public static final int INF = Integer.MAX_VALUE;

    public static void main(String[] args) {
        char[] vertexs = {'A', 'B', 'C', 'D', 'E', 'F', 'G'};
        //克鲁斯卡尔算法的邻接矩阵
        int matrix[][] = {
                /*A*//*B*//*C*//*D*//*E*//*F*//*G*/
                /*A*/ {   0,  12, INF, INF, INF,  16,  14},
                /*B*/ {  12,   0,  10, INF, INF,   7, INF},
                /*C*/ { INF,  10,   0,   3,   5,   6, INF},
                /*D*/ { INF, INF,   3,   0,   4, INF, INF},
                /*E*/ { INF, INF,   5,   4,   0,   2,   8},
                /*F*/ {  16,   7,   6, INF,   2,   0,   9},
                /*G*/ {  14, INF, INF, INF,   8,   9,   0}};
        //大家可以在去测试其它的邻接矩阵，结果都可以得到最小生成树.
        Graph graph = new Graph(vertexs,matrix);
        KruskalCase kruskalCase = new KruskalCase();
        kruskalCase.kruskal(graph);
    }

    public int getEnd(int[] ends , int i){//返回序号为 i 的字符的终点
        while (ends[i] != 0){//如果一条边前面没和任何边连在一起，小顶点的终点是大顶点，大顶点的终点是自己，但是它的ends数组值为0，
            //前面有边连着的话就让小顶点往前找比如原来是<C,D>，现在加入<D,E>,d的终点指向e就行了，再加入<B,C>，c的终点是d,而d终点不为0，继续找D的终点
            //找到E，E的终点为0，说明它是最终点，所以C的终点更新为E，然后E和B的终点B不等，就把E设置为B的终点
            i = ends[i];
        }
        return i;
    }

    public void kruskal(Graph graph){
        List<Edge> edges = graph.getEdges();
        Collections.sort(edges);
        System.out.println(edges);
        int index = 0;
        int[] ends = new int[graph.vertexs.length];//end[i]表示已 i 为起点的边的终点，总是从小到大的如 D->E
        Edge[] results = new Edge[edges.size()];//记录最小生成树

        for (int i = 0; i < edges.size(); i++) {//从最小的边开始取

            int startIndex = graph.getPosition(edges.get(i).start);
            int endIndex = graph.getPosition(edges.get(i).end);

            int i1 = getEnd(ends, startIndex);//获得这条边的两个顶点的终点
            int i2 = getEnd(ends, endIndex);

            if (i1 != i2){//终点一样就成环了
                ends[i1] = i2;//设置 i1 在"已有最小生成树"中的终点 <E,F> [0,0,0,0,5,0,0,0,0,0,0,0],最后的终点的ends值一定是为0的
                results[index++] = edges.get(i);
            }
        }

        for (Edge edge : results){
            System.out.println(edge);
        }
    }
}

class Graph{
    char[] vertexs; //顶点数组
    int[][] matrix; //邻接矩阵

    public Graph(char[] vertexs, int[][] matrix) {
        this.vertexs = vertexs;
        this.matrix = matrix;
    }

    public void print(){
        for (int i = 0; i < vertexs.length; i++) {
            for (int j = 0; j < vertexs.length; j++) {
                System.out.printf("%-12d",matrix[i][j]);
            }
            System.out.println();
        }
    }

    public int getPosition(char ch){//"A" -> 0
        for (int i = 0; i < vertexs.length; i++) {
            if (vertexs[i] == ch)
                return i;
        }
        return -1;
    }

    public List<Edge> getEdges(){//只需要看去掉对角线的上三角就行了,实现comparable接口后treeset自动排序
        List<Edge> edges = new ArrayList<>();
        for (int i = 0; i < vertexs.length; i++) {
            for (int j = i + 1; j < vertexs.length; j++) {
                if (matrix[i][j] != Integer.MAX_VALUE)
                    edges.add(new Edge(vertexs[i], vertexs[j], matrix[i][j]));
            }
        }
        return edges;
    }
}

class Edge implements Comparable<Edge>{
    char start;
    char end;
    int weight;

    public Edge(char start, char end, int weight) {
        this.start = start;
        this.end = end;
        this.weight = weight;
    }

    @Override
    public String toString() {
        return "<" + start + "," + end + "> = " + weight;
    }


    @Override
    public int compareTo(Edge o) {
        return weight - o.weight;
    }
}




